#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

//抽象策略类Sort（抽象排序类）
class Sort{
public:
	virtual vector<int> sort(vector<int> arr) = 0;
}; 

//具体策略类BubbleSort（冒泡排序类）
class BubbleSort : public Sort{
public:
	vector<int> sort(vector<int> arr){
		int len = arr.size();
		for(int i = 0 ; i < len ; i++){
			for(int j = 0 ; j < len ; j++){
                if(arr[i] < arr[j])
				    swap(arr[i],arr[j]);
			}
		}
		cout << "冒泡排序" << endl;
		return arr;
	}
}; 

//具体策略类SelectionSort（选择排序类）
class SelectionSort : public Sort{
public:
	vector<int> sort(vector<int> arr){
		int len = arr.size();
		for(int i = 0 ; i < len ; i++){
			int temp = arr[i];
			int min = i;
			for(int j = i+1 ; j < len ; j++){
				if(arr[j]<temp){
					temp = arr[j];
					min = j;
				}
			}
			swap(arr[i],arr[min]);
		}
		cout << "选择排序" << endl;
		return arr;
	}
}; 

//具体策略类InsertionSort（插入排序类）
class InsertionSort : public Sort{
public:
	vector<int> sort(vector<int> arr){
		int len = arr.size();
		for(int i = 1 ; i < len ; i++){
			int j ;
			int temp = arr[i];
			for(j = i ; i > 0 ; j--){
				if(arr[j-1]>temp){
					arr[j] = arr[j-1];
				}else{
					break;
				}
			}
			arr[j] = temp;
		}
		cout << "插入排序" << endl;
		return arr;
	}
}; 

//环境类ArrayHandler（数组处理类）
class ArrayHandler{
public:
	vector<int> sort(vector<int> arr){
		return sortObj->sort(arr);
	}
	
	void setSortObj(Sort *sortObj){
		this->sortObj = sortObj;
	}
private:
	Sort *sortObj;
}; 

int main(int argv, char**argc)
{
    printf("************  test hello zc!!!   **************\n");
    /* add test code! */

	vector<int> arr = {1,4,6,2,5,3,7,10,9};
	vector<int> result;
	
	//创建数组处理对象 
	ArrayHandler ah;
	
	//设置具体策略 ，这里存在内存泄漏
	ah.setSortObj(new InsertionSort());
	
	//执行排序策略 
	result = ah.sort(arr);
	
	cout << "原来的数组：" << endl;
	for(auto i : arr){
		cout << i << " ";
	}
	
	cout << endl << "排序好的数组：" << endl;
	for(auto i : result){
		cout << i << " ";
	}
	

    
    return 0;
}
